# 给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。
#
#  示例:
#
#  输入: 2
# 输出: 91
# 解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。
class Solution:
    def countNumbersWithUniqueDigits2(self, n: int) -> int:
        """
        解法二：动态规划
        数字位数大于10位的则一定有重复数字
        :param n:
        :return:
        """
        if n == 0:
            return 1
        dp = [0] * (min(10, n) + 1)  # dp[i]= m 代表 长度为 i 的各位数字都不同的数字 x 的个数为m个
        dp[0], dp[1] = 1, 9
        for i in range(2, min(n, 10) + 1, 1):
            dp[i] += dp[i - 1] * (11 - i)  # 前面 i - 1位用了 i - 1 个数字共有dp[i - 1]种情况，最后一位还可以有(11 - i)种数字作为选择
        return sum(dp)

    def countNumbersWithUniqueDigits1(self, n: int) -> int:
        """
        解法一：暴力法，逐个尝试
        数字位数大于10位的则一定有重复数字
        :param n:
        :return:
        """
        def check(num: int) -> bool:
            s = set()
            while num > 0 or num // 10:
                if num % 10 not in s:
                    s.add(num % 10)
                    num = num // 10
                else:
                    return False
            return True

        res = 0
        for i in range(10 ** min(10, n)):
            if check(i):
                res += 1
        return res

    def countNumbersWithUniqueDigits(self, n: int) -> int:
        return self.countNumbersWithUniqueDigits2(n)


if __name__ == "__main__":
    print(Solution().countNumbersWithUniqueDigits(8))  # 2345851
